ATM is emerging as a promising technology for multimedia applications in wired networks. However, much development remains before seamless interworking between wireless (mobile) hosts and wired ATM networks can be offered. One aspect of ATM that requires further development is the problem of routing in ATM-based mobile networks.
As would be understood by a person skilled in the art, ATM is a connection-oriented technology. This implies that there is a connection establishment phase prior to data exchange, and a connection release phase after data exchange. In mobile networks, as end points move, segments of connections need to be torn down and reestablished. Several different connection rerouting methods for hand-offs in mobile networks have been considered in the prior art. Most of these schemes require segment release and setup during hand-offs. Others schemes avoid segment release and setup during hand-offs but require extra segments of a connection tree (from a root switch to a set of base stations to which the mobile could potentially move) to be established during setup.
Connectionless networks completely avoid this problem of having to tear-down and setup segments or establish extra segments for hand-offs. Since routing in connectionless networks is based on end host addresses, a simple update of the current location of the end host is sufficient to handle mobility.
In response to observations regarding this suitability of connectionless networking to support mobility, a networking concept for an ATM-based mobile network ;vas developed by Bell Laboratories to emulate connectionless networks using ATM technology. See, for example, related U.S. patent applications, Ser. No. 08/412,400, entitled A PACKET BASED TELECOMMUNICATIONS NETWORK, filed Mar. 28, 1995, Ser. No. 08,490,980, entitled SIGNALING AND CONTROL ARCHITECTURE FOR AN AD-HOC ATM LAN filed Jun. 15, 1995 and Ser. No. 08/490,981, entitled METHOD AND APPARATUS FOR ROUTING ATM CELLS IN AN AD-HOC ATM LAN, filed Jun. 15, 1995.
Typically, in the commonly adopted connection-oriented usage of ATM, the VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier) fields in the cell header are interpreted as logical channels on ATM links. During connection setup prior to data exchange, translation table entries that map an incoming port/VPI/VCI to an outgoing port/VPI/VCI are created at each transit ATM switch. During data transfer, ATM cells are routed through each switch by matching the VPI/VCI fields of the cell headers with entries in these translation tables.
In the ATM-based mobile network referenced above, also referred to as the BAHAMA LAN, instead of using this common interpretation of the VPI field, VPIs are assigned as addresses of network nodes (switches). All cells with a given VPI are routed to the same destination switch. This is accomplished by preestablishing VPI sink (destination-rooted) trees. Individual connections within a VPI tree are distinguished using VCIs. This type of networking emulates "connectionless" data transfer in that packets are routed as per the destination address in the packet (cell) headers and no explicit segment setup/release is required before/after data exchange or during hand-offs.
FIG. 1 shows an exemplary connectionless ATM-based mobile LAN 10 of the type just described. The network 10 consists of two types of network elements: Portable Base Stations (PBSs) 12 and mobile end points 14. Each PBS 12 combines ATM switching functionality with wireless access interfaces (radio port functionality) providing microcell coverage. Mobile end points 14 are assumed to be portable laptops with wireless ATM capability. The PBSs 12 in FIG. 1 are represented by the numbered boxes and the mobile end points 14 are represented by the X, Y, and Z circles. Also shown in FIG. 1 is the VP/VC 16 usage in the exemplary LAN 10. For example, VPI 9a and VPI 9b are assigned to PBS 9. In other words, all cells with VPI 9a and VPI 9b are routed to the destination PBS 9. Associated with each VPI is a unique route through the network (from each source), thus forming a tree with the destination as the root. To distinguish cells from different connections, each PBS 12 controls the assignment of VCIs associated with VPIs that terminate at that PBS. For example, in FIG. 1, (VPI 9a; VCI 1) and (VPI 9b; VCI 2) denote X-to-Y connections for these mobile end points 14, and (VPI 9a; VCI 3) and (VPI 9b; VCI 4) denote Z-to-Y connections. A simple connection admission (not setup, since there is no hop-by-hop switch configuration prior to data exchange) procedure, consisting of an end-to-end handshake between the source PBS and the destination PBS, is executed to have the destination PBS select a VCI incoming on one of its assigned VPIs. A similar sink tree solution was proposed by R. Cohen, B. V. Patel, F. Schaffa and M.-Villebeek-LeMair, in "The Sink-Tree Paradigm: Connectionless Traffic Support on ATM LANs," Proc. of IEEE Infocom '94, Vol. 2, pp. 821-828, June 1994, for strictly connectionless data networking, however, the sink-tree solution above, however, has no per-connection admission procedure which limits the number of end hosts supported. It also has no mechanisms for supporting QoS guaranteed connections.
VPI trees in the exemplary connectionless ATM-based mobile LAN 10 are allowed to be partial, i.e., not all PBSs 12 in the network are located on every VPI tree. Multiple VPIs are assigned to each PBS to ensure that every PBS is on at least two of the VPI trees (for reliability reasons) assigned to a given destination PBS. Given that the VPI trees are preestablished (provisioned), there is need for a procedure to compute and update the routes of these VPIs with changing conditions in the LAN.
In order to better understand the meaning of provisioning VPI trees, let p.sub.im denote the m.sup.th port of the node i and (p.sub.inv p.sub.jm') represent the physical link between port P.sub.im on PBS i and port p.sub.jm' on PBS j in the direction from PBS i to PBS j. If VPI V is routed through the link (p.sub.inv p.sub.jm'), then a data table called the Transit VPIs data table T.sub.1 is needed in PBS i to map VPI V to port p.sub.im. Each PBS through which VPI V passes needs a corresponding entry for VPI V in its Transit VPIs data table T.sub.1. When an ATM cell arrives at a PBS, the VPI field in the cell header is matched with an entry in table T.sub.1 and the cell routed to the corresponding port. FIG. 2 shows the entries in the Transit VPIs data tables 20 at each PBS 12 through which VPI 9a passes. As can be seen each Transit VPI data table 20 includes a VPI entry 22 and a corresponding port entry 24.
Thus, to provision VPI trees, the routes of these VPI trees must be first computed, and then entries set in the Transit VPIs data table T.sub.1 at each node in the network. Given that the instant ATM mobile LAN supports mobile end points, VPI routes cannot be static and must be constantly updated to meet changing traffic and network conditions. Thus, a routing protocol should include both a computation of initial tree assignments, and a scheme to update these routes.
Besides the Transit VPIs data table T.sub.1, each PBS stores other data tables to support the control and management plane algorithms of the subject ATM mobile LAN. A list of exemplary tables is shown in Table 1. The Port/capacity data table T.sub.2 stores the identifier of the PBS connected to each of its ports. Also, for each port, it stores the link capacity and the current usage value. Since VPI trees are allowed to be partial, in that only a subset of PBSs may be located on a VPI tree terminating at a given PBS P, a third table T.sub.3, the Destination-VPIs table lists the identifiers of all the PBSs located on each of the VPI trees rooted at PBS Finally, given a destination PBS ID, a source PBS may be located on one or more VPI trees terminating at the destination PBS. The PBS-to-VPIs mapping table, T.sub.4, stores this information.
An extension to the above-stated problem (compute the routes of initial VPI trees and then update these routes as network and traffic conditions change) is to determine resource allocation for these VPI trees. In typical ATM networks, virtual path connections are provisioned between pairs of switches a priori and allocated bandwidth. Several algorithms have been proposed to perform effective a priori bandwidth allocation to these virtual path connections. The question of whether bandwidth (and other resources) can be allocated a priori in a "VPI trees-based network" is related to the control plane schemes used in the subject ATM mobile LAN. In "A Wireless Broadband Ad-Hoc ATM Local-Area Network," by K. Y. Eng, M. J. Karol, M. Veeraraghavan, E. Ayanoglu, C. B. Woodworth, P. Pancha, and R. A. Valenzuela, ACM/Baltzer Journal on Wireless Networks, vol. 1, no. 2, 1995, two control plane schemes were described for providing QoS guarantees during connection admission. The first scheme is to perform a hop-by-hop resource checking procedure along the route of the VPI tree before admitting the connection. This scheme requires no bandwidth preallocation. The second scheme is to preallocate a priori link (bandwidth) and node (buffer) resources to each PBS, for all the links and nodes in the network. During connection admission, the root PBS checks its allocations for each link and node on the route from the source PBS to itself to verify resource availability for the requested QoS measures. Based on which scheme is assumed in the control plane, the problem statement of maintaining VPI trees includes or excludes the a priori bandwidth allocation aspect. Let us assume that the present invention assumes the first control plane scheme, which requires no a priori bandwidth allocation. Thus, the problem to be solved by is simply to compute the routes of the initial VPI trees, program the data tables, and update these routes as needed. Existing routing protocols are not, however, practically applicable to the problems/requirements of the described connectionless ATM mobile LAN.
Routing in ATM networks that use the traditional interpretation of VPI/VCIs is handled in many different ways. In such networks, since a connection is established before data transfer, no per-node route determination is required for the ATM cells. Routing in the user plane becomes simply a matter of matching the VPI/VCI fields of the cell headers with entries in the port/VPI/VCI translation tables (that are set and cleared by control plane signaling procedures during connection setup and release) stored at each switch on the end-to-end route. However, a routing problem exists in the control plane. During connection setup, upon receiving signaling messages requesting a connection, each ATM switch needs to determine the route to reach the destination and thus select the appropriate outgoing port for the connection.
Two approaches to table-based routing that are applicable to ATM networks have been described by C. Baransel, W. Dobosiewicz and P. Gburzynski, "Routing in Multihop Packet Switching Networks: Gb/s Challenge," IEEE Network Magazine, pp. 38-61, 1995, optimal routing and shortest-path routing. The optimal table-based routing scheme uses a network manager to compute routes based on current loading conditions and predicted call arrival/departure patterns. This typically involves periodically solving a network-wide optimization problem for some objective function, such as blocked call rate, subject to a set of constraints. The computed routes are then downloaded to the switches. When a signaling request for a connection setup arrives at a switch, it simply consults its routing table (that was preloaded by the routing procedure) to determine the next switch in the route. In ATM networks, the ITU-T signaling standard for public ATM networks assumes that routing data is somehow available to switches. There is, however, no counterpart ITU-T standard to dynamically determine the route. For small networks, routing data can be entered manually, but for large networks, it is assumed that routing tables are computed by one or more centralized traffic management stations using this optimal routing scheme.
A second approach is the shortest-path table-based routing scheme which is used in the PNNI (Private Network Node/Network Interface) routing protocol defined by the ATM Forum in 94-0471R9, "Private-Network Node Interface Phase 1 Draft Specification". Here, periodic topology state packets are exchanged between ATM switches. When a signaling request for connection setup arrives at a switch, it uses the network topology and state information (updated by the PNNI routing protocol) to select a set of switches through which to route the connection using an on-the-fly path determination algorithm, such as Dijkstra's shortest path algorithm. Hierarchical ordering of ATM switches (for example, peer groups) is used to scale this procedure for large networks.
A combination of these two schemes is to have virtual path connections (VPCs) provisioned between every pair of ATM switches. Bandwidth allocation and routing of these VPCs are typically determined using centralized optimizations. Most on-demand connections are then routed on these direct links (VPCs). In addition, in case the direct link is fully loaded, dynamic routing schemes, such as Least Loaded Routing (LLR), "Routing in Communications Networks," M. Steenstrup, Editor, Prentice Hall 1995, Chapter 2, can be used to find alternate paths (routed through one via switch). This latter step can be viewed as a shortest-path computation.
None of the above three approaches (optimal, shortest-path, or combination) is practically adoptable in the connectionless ATM mobile LAN for the following reasons. First, the optimal table-based routing scheme and the combination scheme require a centralized management station, which is counter to important goals of "simplicity and low-cost" in the ATM mobile LAN. Next, the shortest-path table-based approach can be used, but would require a "three-phase" solution to the problem. In other words, to emulate connectionless networking, there should be no "connection setup" phase for hop-by-hop switch configurations prior to data exchange. This is counter to the shortest-path scheme which is based on determining the routes of connections during connection setup. Thus, to be able to use the PNNI routing scheme, a three-phase approach is required: first, topology state packets are exchanged periodically; second, based on this information, synchronous route computations are required to setup the VPI trees (configure fabrics with Transit VPIs data table ), third, connection admission is used to select a VCI and a VPI tree for the connection prior to data exchange. As would be understood, this three-phase solution may be avoided by using a distance-vector based algorithm, like RIP (Routing Information Protocol), "Routing in Communications Networks," M. Steenstrup, Editor, Prentice Hall 1995, Chapter 3, rather than a link-state algorithm for the routing protocol.
RIP is a commonly used routing protocol in connectionless (IP) networks. However, there are two reasons why RIP is not suitable for use in the connectionless ATM mobile LAN. First, unlike IP networks, ATM networks guarantee sequenced delivery. This implies that asynchronous updates of routing data in nodes cannot be permitted. Secondly, in IP networks, if a link fails, and an arriving IP packet needs to be routed on the failed link (as per the routing data), the node can always use other neighbors to forward this IP packet. In the subject ATM mobile LAN, this flexibility is not available, since ATM cell sequence needs to be maintained. In other words, in table T1 there is only one port corresponding to each VPI, with no alternative options. This, in turn, creates a need to provision at least two disjoint end-to-end paths between every pair of nodes, a constraint not met by RIP.
Given the constraints of maintaining sequenced delivery and requiring disjoint paths, it can be seen that none of the existing routing protocols described above is suitable for use in a type of connectionless ATM mobile LAN, similar to the BAHAMA LAN. Accordingly, there is need for a new routing protocol for this type of ATM-based wireless network which is capable of adapting to changing conditions therein.